The present invention relates to a method and an apparatus for post-processing a raw bit sequence of a noise source.
A random number generator generates an output signal, which consists of a sequence of random numbers, typically represented by a random bit stream. Random number generators can be grouped into pseudo random number generators and true random number generators. In pseudo random number generators, random numbers are generated out of an initial state, the so-called seed, by applying a predetermined algorithm. As a result, uniformly distributed random numbers are achieved. However, given the complete knowledge of the generator structure and previously generated random number sequences, it is possible to predict following random numbers. That is, pseudo random number generators lack independence between consecutively generated random words.
The lack of independence is not acceptable in sensible security applications, in which an observer or even attacker must not be able to carry out any useful predictions about the output of the random number generator—even if the design of the random number generator is known. For true random number generators, the generated random numbers are not predictable, i.e. the above requirement is fulfilled. In a true random number generator, the random bit stream is generated from a non-deterministic natural source like electronic noise. One possible non-deterministic natural source is for example a sampling of a jittered oscillator, the corresponding hardware producing random numbers to a very high rate.
Although natural sources exhibit, in principle, true randomness, in concrete technical realizations the statistical quality of the generated random numbers is limited due to bandwidth limitation, fabrication tolerances, aging and temperature drifts. To improve the statistic quality, i.e. to get closer to true randomness, a digital post-processing device conventionally follows the non-deterministic noise source. This post-processing generates random words from consecutive sub-sequences of the sequence of random numbers and normally involves also a compression of the bit stream, i.e. the output random word comprises fewer bits than the input sub-sequence of bits used therefore.
Among noise sources, one distinguishes memory-less or state-less noise sources from noise sources which keep to a certain degree the memory to previously generated bit sequences and hence are not memory-less. Under the hypothesis of independence of the input raw sub-sequences coming from a memory-less noise source, a conventional compression algorithm guarantees the independence of the generated random words, thus allowing the verification of a minimal entropy limit directly after the post processor. If, however, the available noise source is not memory-less (for example if a feedback strategy to improve the robustness against technological and environmental variation is employed), the conventional approach is not sufficient to prove that the output (compressed) random words are independent. An example for a not memory-less noise sources is an offset compensated oscillator-based random bit generator.